/**
 * @param {string} s
 * @return {number}
 */
var isPalindrome = function (s, left, right) {
    while (left <= right) {
        if (s[left] !== s[right]) {
            return false
        }
        left++
        right--
    }
    return true
}
var minCut = function (s) {
    if (isPalindrome(s, 0, s.length - 1)) return 0
    let res = s.length
    const path = []
    const len = s.length
    const dfs = function (i) {
        if (i === len) {
            if (path.length < res) {
                res = path.length
            }
            return
        }
        for (let j = i; j < len; j++) {
            if (isPalindrome(s, i, j)) {
                path.push(s.substring(i, j + 1))
                dfs(j + 1)
                path.pop()
            }
        }
    }
    dfs(0)
    return res - 1
};